﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Navigation;

namespace OneOfAll.Common.Bussiness
{
    public class Node
    {
        public int x;
        public int y;
        public bool isWalkable;
        /// <summary>
        /// 优先级值
        /// </summary>
        public int fCost { get { return hCost + gCost; } }
        /// <summary>
        /// 该点到终点预测的值(无视障碍和难度)
        /// </summary>
        public int hCost;
        /// <summary>
        /// 耗费值 起点到该点要耗费的值
        /// </summary>
        public int gCost;
        public Node parent;
        public int difficulty = 1;
        public int step = 0;

        public Node(int x, int y, bool isWalkable, int difficulty = 1)
        {
            this.x = x;
            this.y = y;
            this.isWalkable = isWalkable;
            this.difficulty = difficulty;
        }
    }

    public class PathHelper
    {
        private Node[,] allNodes;
        
        public PathHelper(Node[,] nodeArray)
        {
            allNodes = nodeArray;
        }

        public List<Node> FindPath(Node startNode, Node targetNode, int maxStep = 0)
        {
            //需要计算的节点集合
            List<Node> openList = new List<Node>();
            //计算完毕的节点集合
            byte[,] closeArray = new byte[allNodes.GetLength(0), allNodes.GetLength(1)];
            //加入起点
            openList.Add(startNode);
            while (openList.Count > 0)
            {
                //根据F和G排序
                Node currentNode = openList[0];
                openList.Remove(currentNode);
                closeArray[currentNode.x, currentNode.y] = 1;
                if (currentNode.x == targetNode.x && currentNode.y == targetNode.y)
                {
                    return RetracePath(startNode, currentNode);
                }
                foreach (Node neighbor in GetNeighbors(currentNode, targetNode))
                    {
                    if (!neighbor.isWalkable || closeArray[neighbor.x, neighbor.y] == 1)
                        continue;
                    if (currentNode.step + 1 > maxStep && maxStep > 0) continue;
                    neighbor.gCost = currentNode.gCost + GetDistance(currentNode, neighbor);
                    neighbor.hCost = GetDistance(neighbor, targetNode);
                    neighbor.parent = currentNode;
                    neighbor.step = currentNode.step + 1;
                    var tempNode = openList.FirstOrDefault(t => t.x == neighbor.x && t.y == neighbor.y);
                    if (tempNode == null)
                    {
                        if (openList.Count == 0)
                            openList.Add(neighbor);
                        else if (neighbor.fCost < openList[0].fCost || (neighbor.fCost == openList[0].fCost && neighbor.gCost < openList[0].gCost))
                            openList.Insert(0, neighbor);
                        else
                            openList.Add(neighbor);
                    }
                    else if (tempNode.fCost > neighbor.fCost)
                        tempNode = neighbor;
                }
            }

            return null;
        }

        //根据Start和End节点获取路径
        private List<Node> RetracePath(Node startNode, Node endNode)
        {
            List<Node> path = new List<Node>();
            Node currentNode = endNode;

            while (currentNode.x != startNode.x  || currentNode.y != startNode.y)
            {
                path.Add(currentNode);
                currentNode = currentNode.parent;
                //currentNode = allNodes[currentNode.parentX, currentNode.parentY];
            }

            path.Reverse();
            return path;
        }

        private List<Node> GetNeighbors(Node node, Node targetNode)
        {
            // 根据具体情况实现获取相邻节点的逻辑
            List<Node> neighbors = new List<Node>();

            // 添加上、下、左、右四个方向的相邻节点
            int dx = targetNode.x - node.x;
            int dy = targetNode.y - node.y;
            if (dx >= 0 && dy >= 0)
            {
                if (Math.Abs(dx) > Math.Abs(dy))
                {
                    GetNeighbor(node, neighbors, 1);
                }
                else
                {
                    GetNeighbor(node, neighbors, 2);
                }
            }
            else if (dx >= 0 && dy < 0)
            {
                if (Math.Abs(dx) > Math.Abs(dy))
                {
                    GetNeighbor(node, neighbors, 1);
                }
                else
                {
                    GetNeighbor(node, neighbors, 0);
                }
            }
            else if (dx < 0 && dy >= 0)
            {
                if (Math.Abs(dx) > Math.Abs(dy))
                {
                    GetNeighbor(node, neighbors, 3);
                }
                else
                {
                    GetNeighbor(node, neighbors, 2);
                }
            }
            else
            {
                if (Math.Abs(dx) > Math.Abs(dy))
                {
                    GetNeighbor(node, neighbors, 3);
                }
                else
                {
                    GetNeighbor(node, neighbors, 0);
                }
            }

            //if (node.y + 1 < allNodes.GetLength(1))
            //    neighbors.Add(allNodes[node.x, node.y + 1]);
            //if (node.y - 1 >= 0)
            //    neighbors.Add(allNodes[node.x , node.y - 1]);
            //if (node.x + 1 < allNodes.GetLength(0))
            //    neighbors.Add(allNodes[node.x + 1, node.y]);
            //if (node.x - 1 >= 0)
            //    neighbors.Add(allNodes[node.x - 1, node.y]);

            return neighbors;
        }

        private List<Node> GetNeighbors(Node node)
        {
            // 根据具体情况实现获取相邻节点的逻辑
            List<Node> neighbors = new List<Node>();

            // 添加上、下、左、右四个方向的相邻节点
            //GetNeighbor(node, neighbors, 2);
            //GetNeighbor(node, neighbors, 0);
            //GetNeighbor(node, neighbors, 3);
            //GetNeighbor(node, neighbors, 1);

            if (node.y + 1 < allNodes.GetLength(1))
                neighbors.Add(allNodes[node.x, node.y + 1]);
            if (node.y - 1 >= 0)
                neighbors.Add(allNodes[node.x, node.y - 1]);
            if (node.x + 1 < allNodes.GetLength(0))
                neighbors.Add(allNodes[node.x + 1, node.y]);
            if (node.x - 1 >= 0)
                neighbors.Add(allNodes[node.x - 1, node.y]);
            return neighbors;
        }

        /// <summary>
        /// 根据方向获取临近点
        /// </summary>
        /// <param name="node">当前点</param>
        /// <param name="direction">方向 0-上 1-右 2-下 3-左</param>
        /// <returns></returns>
        public void GetNeighbor(Node node, List<Node> neighbors, int direction)
        {
            for (int i = 0; i < 4; i++)
            {
                int x = -1, y = -1;
                switch ((direction + i) % 4)
                {
                    case 0:
                        if (node.y + 1 > 0)
                        {
                            x = node.x;
                            y = node.y - 1;
                        }
                        break;
                    case 1:
                        if (node.x + 1 < allNodes.GetLength(0))
                        {
                            x = node.x + 1;
                            y = node.y;
                        }
                        break;
                    case 2:
                        if (node.y + 1 < allNodes.GetLength(1))
                        {
                            x = node.x;
                            y = node.y + 1;
                        }
                        break;
                    case 3:
                        if (node.x - 1 >= 0)
                        {
                            x = node.x - 1;
                            y = node.y;
                        }
                        break;
                }
                if (x >= 0 && x < allNodes.GetLength(0) && y >= 0 && y < allNodes.GetLength(1))
                    neighbors.Add(allNodes[x, y]);
            }
        }

        private int GetDistance(Node nodeA, Node nodeB)
        {
            int dstX = Math.Abs(nodeA.x * nodeA.difficulty - nodeB.x * nodeB.difficulty);
            int dstY = Math.Abs(nodeA.y * nodeA.difficulty - nodeB.y * nodeB.difficulty);

            return dstX + dstY;
        }
    }
}
